﻿//给你一个整数数组 nums ，按要求返回一个新数组 counts 。
//数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
//
//输入：nums = [5, 2, 6, 1]
//输出：[2, 1, 1, 0]
//解释：
//	5 的右侧有 2 个更小的元素(2 和 1)
//	2 的右侧仅有 1 个更小的元素(1)
//	6 的右侧有 1 个更小的元素(1)
//	1 的右侧有 0 个更小的元素
//
//输入：nums = [-1]
//输出：[0]
//
//输入：nums = [-1, -1]
//输出：[0, 0]
//
//提示：
//	1 <= nums.length <= 10^5
//	- 10^4 <= nums[i] <= 10^4

class Solution {
    vector<int> ret;
    vector<int> index; // 记录nums中当前元素的原始下标

    int tmpNums[500010];
    int tmpIndex[500010];

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n);
        index.resize(n);
        // 初始化⼀下index数组

        for (int i = 0; i < n; i++)
            index[i] = i;
        mergeSort(nums, 0, n - 1);
        return ret;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right)
            return;
        // 1.根据中间元素，划分区间

        int mid = (left + right) >> 1;
        // [left, mid]  [mid + 1, right]
        // 2.先处理左右两部分

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        // 3.处理⼀左⼀右的情况

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) // 降序

        {
            if (nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }
            else {
                ret[index[cur1]] += right - cur2 + 1; // 重点

                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        // 4.处理剩下的排序过程

        while (cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }
        for (int j = left; j <= right; j++) {
            nums[j] = tmpNums[j - left];
            index[j] = tmpIndex[j - left];
        }
    }
};